class Solution {
    public int rob(int[] nums) {
        // 分类讨论：是否选择偷窃0下标
        // 偷窃0下标
        int n = nums.length;
        int ret1 = robIndex(nums, 2, n-2) + nums[0];
        // 不偷窃0下标
        int ret2 = robIndex(nums, 1, n-1);
        return Math.max(ret1, ret2);
    }

    // 偷窃 [a,b] 内的钱
    private int robIndex(int[] nums, int a, int b) {
        // 创建 dp 表、初始化、填表、返回值
        // 排除特殊情况
        if (a > b) {
            return 0;
        }
        int n = b-a+1;
        int[] f = new int[n];
        int[] g = new int[n];

        f[0] = nums[a];

        for (int i = 1; i < n; i++) {
            f[i] = g[i-1] + nums[a+i]; // 注意这里的下标映射关系
            g[i] = Math.max(f[i-1], g[i-1]);
        }

        return Math.max(f[n-1], g[n-1]);
    }
}